#include <math.h>
#include <assert.h>

#include <fstream>
#include <iostream>

#include "../contree/disjointset.h"
#include "../sdf/dynarray.h"
#include "dualgraph.h"

using namespace PBVP;

DualGraph::DualGraph(float min, float max, int nr) {
	// the number of functional intervals must be positive.
	n_Ranges = nr;

	if (nr > 0)
	{
		nodes = new dynamic_array<DualNode*>[n_Ranges];
		cut_vals = new float[n_Ranges+1];
	} else
	{	 // useful for loading from file
		nodes = NULL;
		cut_vals = NULL;
	}
	nnodes = 0;
	m_min = min;
	m_max = max;
}



DualGraph* DualGraph::mergeRanges()
{
	// assume nrange is power of 2
	DualGraph* dual = new DualGraph(m_min, m_max, n_Ranges/2);
	dual->m_min = m_min;
	dual->m_max = m_max;

	int i, j, k, n;

	std::map<int, int> refs;
	std::map<int, DualNode *> dualrefs;
	int cur_id = 0;
	for (i = 0; i < n_Ranges/2; i++)
	{
		DisjointSet *djs = new DisjointSet(nodes[2*i].size() + nodes[2*i+1].size());
		for (j = 0; j < nodes[2*i].size(); j++)
		{
			refs[(nodes[2*i])[j]->id] = j;
			djs->makeSet(j);
		}
		for (k = 0; k < nodes[2*i+1].size(); k++, j++)
		{
			refs[(nodes[2*i+1])[k]->id] = j;
			djs->makeSet(j);
			int ngb = (nodes[2*i+1])[k]->lowerDegree();
			for (n = 0; n < ngb; n++)
			{
				int nid = (nodes[2*i+1])[k]->lowerNeighbor(n)->id;
				djs->unionSet(j, refs[nid]);
			}
		}
		for (j = 0; j < (nodes[2*i]).size(); j++)
		{
			DualNode *dualnode;
			int dual_id = djs->find(j);
			// a new node
			if (dualrefs.find(dual_id) == dualrefs.end())
			{
				dualnode = new DualNode(i);
				dualnode->id = cur_id++;
				dualrefs[dual_id] = dualnode;
				dual->insert(i, dualnode);
				dualnode->merge((nodes[2*i])[j], 0, true);
			} else	// merge to an existing node
			{
				dualnode = dualrefs[dual_id];
				dualnode->merge((nodes[2*i])[j], 0, false);
			}

		}

		for (j = 0; j < (nodes[2*i+1]).size(); j++)
		{
			DualNode *dualnode;
			int dual_id = djs->find(j+nodes[2*i].size());
			if (dualrefs.find(dual_id) == dualrefs.end())
			{
				dualnode = new DualNode(i);
				dualnode->id = cur_id++;
				dualrefs[dual_id] = dualnode;
				dual->insert(i, dualnode);
				dualnode->merge((nodes[2*i+1])[j], 1, true);
			} else
			{
				dualnode = dualrefs[dual_id];
				dualnode->merge((nodes[2*i+1])[j], 1, false);
			}
		}
		refs.clear();
		dualrefs.clear();
		delete djs;
	}

	// connect the coarsers dual graph
	for (i = 0; i < n_Ranges/2-1; i++)
	{
		for (j = 0; j < nodes[2*i+1].size(); j++)
		{
			int ngb = (nodes[2*i+1])[j]->upperDegree();
			for (n = 0; n < ngb; n++)
			{
				DualNode::connect((nodes[2*i+1])[j]->parent, (nodes[2*i+1])[j]->upperNeighbor(n)->parent);
				//(nodes[2*i+1])[j]->parent->addUpperNeighbor((nodes[2*i+1])[j]->ngb_us[n]->parent);
				//(nodes[2*i+1])[j]->ngb_us[n]->parent->addLowerNeighbor((nodes[2*i+1])[j]->parent);
			}
		}
	}
	return dual;
}

void DualGraph::print()
{
	int i, j;
	int count = 0;
	for (i = 0; i < n_Ranges; i++)
	{
		printf("Range %d .........................................\n", i);
		for (j = 0; j < nodes[i].size(); j++)
		{
			(nodes[i])[j]->print();
			count ++;
		}
	}
	printf("The number of nodes: %d\n", count);
}

QString DualGraph::toQString() const
{
	QString out;

	for(int i = 0; i < n_Ranges; i++) 
	{
		out.append(QString("---------------------------- Range %1 ---------------------------------- \n").arg(i));
		out.append(QString("%1 nodes in this range\n").arg(nodes[i].size())); 

		// sort nodes in the range by their volumes
		std::vector<DualNode *> node_vec;
		for(int j = 0; j < nodes[i].size(); j++)
		{
			node_vec.push_back((nodes[i])[j]);
		}
		std::sort(node_vec.begin(), node_vec.end(), Less_DualNodePtr());
		std::vector<DualNode *>::reverse_iterator rit;
		for(rit = node_vec.rbegin(); rit != node_vec.rend(); ++rit)
		{
			out.append("\n");
			out.append((*rit)->toQString());
		}
	}
	
	return out;
}

void DualGraph::saveFile(const char* fname)
{
	std::ofstream out(fname);
	// -- newer version 6 (June 6, 2007)
	out << 6 << std::endl;

	int i, j;
	int nr = numOfRanges();
	int nn = totalNodes();

	// number of ranges and total number of nodes
	out << nr << " " << nn << std::endl;
	out << m_min << " " << m_max << std::endl;
	// number of nodes in each level
	for (i = 0; i < nr; i++)
	{
		out << nodes[i].length() << " ";
	}
	out << std::endl;

	// output individual nodes
	for (i = 0; i < nr; i++)
	{
		for (j = 0; j < numOfNodes(i); j++)
		{
			out << *((nodes[i])[j]);
		}
	}
	out.close();        
}

void DualGraph::prune(float threshold) 
{
	int i, nd = nnodes;

	// The coarsest level
	if (n_Ranges == 1)
	{
		dynamic_array<DualNode *> tnode;
		tnode.insert(nodes[0]);
		nodes[0].clear();

		for (i = 0; i < nd; i++)
		{
			if (tnode[i]->getNormalizedVolume() >= threshold)
			{
				//printf("accepted volume = %f\n", tnode[i]->volume);
				nodes[0].insert(tnode[i]);
			} else
			{
				//printf("pruned volume = %f\n", tnode[i]->volume);
				pruned.insert(tnode[i]);
				tnode[i]->pruned = true;
				nnodes --;
			}
		}
	} else
	{
		// For other levels, a node is pruned if its parent is pruned
		int nr;
		for (nr = 0; nr < n_Ranges ; nr++)
		{
			dynamic_array<DualNode *> tnode;
			tnode.insert(nodes[nr]);
			nd = nodes[nr].length();
			nodes[nr].clear();
			for (i = 0; i < nd; i++)
			{
				if (tnode[i]->parent->pruned)
				{
					// prune
					pruned.insert(tnode[i]);
					tnode[i]->pruned = true;
					nnodes --;
				} else
				{
					nodes[nr].insert(tnode[i]);
				}
			}
		}
	}
}


bool DualGraph::loadFile(const char* fname)
{
	std::ifstream in(fname);
	if (!in.is_open())
	{
		std::cerr << "cannot open file " << fname << std::endl;
		return false;
	}

	int head;
	in >> head;
	if (head != 6)
	{
		std::cerr << "Dual Contour Tree version mismatch, recreating the DCT\n";
		std::cerr << "Verison 6 is expected\n";
		in.close();
		return false;
	}

	clean();

	// read number of ranges and total number of nodes
	in >> n_Ranges >> nnodes;
	in >> m_min >> m_max;

	int i, j, k;
	nodes = new dynamic_array<DualNode*>[n_Ranges];
	cut_vals = new float[n_Ranges+1];
	// allocate space for the nodes
	DualNode **arry = (DualNode **) malloc(sizeof(DualNode*)*nnodes);
	for (i = 0; i < nnodes; i++)
	{
		arry[i] = new DualNode;
	}

	for (i = 0, k = 0; i < n_Ranges; i++)
	{
		int nn; 
		in >> nn;
		for (j = 0; j < nn; j++, k++)
		{
			nodes[i].insert(arry[k]);
		}
	}

	for (i = 0; i < n_Ranges; i++)
	{
		for (j = 0; j < nodes[i].length(); j++)
		{
			DualNode* dualnode = (nodes[i])[j];
			// read in node 
			in >> *dualnode;
			// read neighboring information
			int nl, nu, nid;
			in >> nl >> nu;
			for (k = 0; k < nl; k++)
			{
				in >> nid;
				dualnode->addLowerNeighbor(arry[nid]);
			}
			for (k = 0; k < nu; k++)
			{
				in >> nid;
				dualnode->addUpperNeighbor(arry[nid]);
			}
		}
	}
	in.close();
	free(arry);
	return true;
}

void DualGraph::clean()
{
	int i, j;
	for (i = 0; i < n_Ranges && nodes != NULL; i++)
	{
		for (j = 0; j < nodes[i].length(); j++)
		{
			delete (nodes[i])[j];
		}
	}
	delete[] nodes;
	delete[] cut_vals;
	for (i = 0; i < pruned.size(); i++)
	{
		delete pruned[i];
	}
}

DualGraph::~DualGraph()
{
	clean();    
}
